package com.xiayuanxing.arithmetic.Algorithm.prim;

import java.util.Arrays;

/**
 * @projectName: arithmetic
 * @className: PrimAlgorithm
 * @author: xiayuanxing
 * @description: 普利姆算法解决修路问题
 * @date: 2021/11/30 10:52
 * @version: 1.0
 */
public class PrimAlgorithm {

    public static void main(String[] args) {
        char[] data = new char[]{'A','B','C','D','E','F','G'};
        int verxs = data.length;
        //邻接矩阵的关系使用二维数组表示。10000这个大数，表示两个点不连通
        int[][] weight = new int[][]{
                {10000,5,7,10000,10000,10000,2},
                {5,10000,10000,9,10000,10000,3},
                {7,10000,10000,10000,8,10000,10000},
                {10000,9,10000,10000,10000,4,10000},
                {1000,10000,8,10000,10000,5,4},
                {10000,10000,10000,4,5,10000,6},
                {2,3,10000,10000,4,6,10000}};

        //创建MGraph对象
        MGraph graph = new MGraph(verxs);
        //创建一个MinTree对象
        MinTree minTree = new MinTree();
        minTree.cvreateGraph(graph,verxs,data,weight);
        minTree.showGraph(graph);


        //测试普利姆算法
        minTree.prim(graph,0);


    }
}

/**
 * @return null
 * @author xiayuanxing
 * @description 创建最小生成树->村庄的图
 * @date 2021/11/30 11:03
 */
class MinTree{
    
    /**
     * @param graph: 图对象
     * @param verxs: 图对应的顶点个数
     * @param data: 图的各个顶点的值
     * @param weight: 图的邻接矩阵
     * @return void
     * @author xiayuanxing
     * @description TODO
     * @date 2021/11/30 11:05
     */
    public void cvreateGraph(MGraph graph,int verxs,char[] data,int[][] weight){
        int i,j;
        for (i = 0;i < verxs; i ++){
            graph.data[i] = data[i];
            for (j = 0;j < verxs;j ++){
                graph.weight[i][j] = weight[i][j];
            }
        }
    }

    /**
     * @param graph:
     * @return void
     * @author xiayuanxing
     * @description 显示图的邻接矩阵
     * @date 2021/11/30 11:14
     */
    public void showGraph(MGraph graph){
        for (int[] link : graph.weight) {
            System.out.println(Arrays.toString(link));
        }
    }

    public void prim(MGraph graph,int v){

        //visited表示结点（顶点）是否被访问过
        int[] visited = new int[graph.verxs];

        //把当前这个结点标记为已访问
        visited[v] = 1;
        //h1和h2记录两个顶点的下标
        int h1 = -1;
        int h2 = -1;
        //将minWeight 初始成一个大数，在后面的遍历过程中会被替换
        int minWeight = 10000;
        //因为有graph.verxs顶点，普利姆算法结束后，有graph.verxs - 1条边
        for (int k = 1; k < graph.verxs; k++) {

            //这个是确定每次生成的子图，和那个结点的距离最近
            //i结点表示被访问过得结点
            for (int i = 0; i < graph.verxs; i++) {
                //j结点表示没有被访问的结点
                for (int j = 0; j < graph.verxs; j++) {
                    if (visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight){
                        //替换minWeight（寻找已经访问过的结点和未访问过的结点间的权值最小的边）
                        minWeight = graph.weight[i][j];
                        h1 = i;
                        h2 = j;
                    }
                }
            }

            //当退出这个循环时，表示找到了最小的那一条边
            System.out.println("边<"+graph.data[h1]+","+graph.data[h2]+">权值："+minWeight);
            //将当前找到的节点标记为已访问
            visited[h2] = 1;
            //minWeight重置
            minWeight = 10000;

        }
    }
    
}


class MGraph{


    /** 表示图的节点个数 */
    int verxs;
    /** 存放节点数据 */
    char[] data;
    /** 存放边，指的是邻接矩阵 */
    int[][] weight;

    /**
     * @param verxs:
     * @return null
     * @author xiayuanxing
     * @description 初始化
     * @date 2021/11/30 10:59
     */
    public MGraph(int verxs){
        this.verxs = verxs;
        data = new char[verxs];
        weight = new int[verxs][verxs];
    }
}
